Video muzik ini telah diarah oleh pengarah video muzik UK, Sophie Muller. Video muzik ini menunjukkan Björk di dalam sebuah dapur, sedang mengusap sebiji telur dan berfikir cara yang paling sesuai untuk memasaknya (antara cara yang difikirkan ialah seperti merebusnya). Akhirnya, beliau menggoreng telur tersebut. Video ini berakhir dengan beliau memegang sebuah cicak peliharaan dan dikelilingi oleh kilauan.

Walau bagaimanapun, Björk telah mengatakan kekecewaannya kerana telur di dalam video tersebut akhirnya digoreng dalam sebuah temubual[5]. Beberapa hari sebelum penggambaran video muzik tersebut, beliau telah memberi sebuah buku yang mengilhamkan "Venus As A Boy" iaitu Story Of The Eye karya Georges Bataille kepada Sophie Muller, namun pengarah tersebut tidak mempunyai masa untuk membaca novel itu. Setelah penggambaran video dan membaca buku tersebut, Sophie Muller akhirnya berpendapat telur goreng bukanlah "telur yang sesuai".

Di samping itu, kebanyakan alatan harian di dalam dapur video "Venus As A Boy" adalah kepunyaan Björk sendiri[6].

Bahagian telur video ini juga telah dimasukkan ke dalam sketsa parodi dalam rancangan French & Saunders, dibintangi oleh Dawn French dan Jennifer Saunders.